<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 节点
        class ListNode {
            constructor(val) {
                this.value = val;
            }
        }
        //实现以下功能
        // get(index) 获取 第 index 节点的值
        // addAtHead(val) 在链表最前边加入一个 值为 val 的节点
        // addAtTail(val) 在链表最后加入一个 值为 val 的节点
        // addAtIndex(index,val) 在链表第 index 节点之前加入一个 值 为 val的节点
        // delete(index) 删除链表第 index 节点
        // 链表
        class LinkedList {
            constructor() {
                this.head = null;
                this.tail = null;
                this.length = 0;
            }
            get(index) {
                var cur = this.head;
                var i = 0;
                while (i < index) {
                    cur = cur.next;
                    i++;
                }
                return cur.val;
            }
            addAtHead(val) {
                var lastHead = this.head;
                var node = new ListNode(val);
                this.head = node;
                this.head.next = lastHead;
                if (!this.tail) {
                    // 说明之前链表没有元素
                    this.tail = node;
                    this.tail.next = null;
                }
                this.length++;
            }

            addAtTail(val) {

                var node = new ListNode(val);
                node.next = null;
                var lastTail = this.tail;
                lastTail.next = node;
                this.tail = node;
                if (!this.head) {
                    this.head = node;
                }
                this.length++;
            }
            addAtIndex(index, val) {
                if (index == this.length) {
                    this.addAtTail(val)
                } else if (index == 0) {
                    this.addAtHead(val)
                } else {

                    // var cur = this.head;
                    // var prev;
                    // var i = 0;
                    // while (i < index) {
                    //     prev = cur;
                    //     cur = cur.next;
                    //     i++
                    // }
                    // var node = new ListNode(val)
                    // node.next = cur;
                    // prev.next = node;

                    // 优化
                    var prev = this.head;
                    var i = 0;
                    while (i < index - 1) {
                        prev = prev.next;
                        i++;
                    }
                    var node = new ListNode(val);
                    node.next = prev.next;
                    prev.next = node;
                    this.length++;

                }
            }
            delete(index) {
                if (index == 0) {
                    this.head = this.head.next;
                    this.length--;
                } else if (index > 0 && index < this.length) {
                    var cur = this.head;
                    var prev;
                    var i = 0;
                    while (i < index) {
                        prev = cur;
                        cur = cur.next;
                        i++
                    }
                    prev.next = cur.next;
                    if (this.length - 1 == index) {
                        this.tail = prev;
                    }
                    this.length--;
                }
            }
        }


    </script>
</body>

</html>